끝말잇기를 하다 보면 문득 궁금해집니다. "지금 이 상황에서, 내가 무조건 이길 수 있는 방법이 있을까?" 즉, 어떤 음절 가 주어졌을 때, 그 포지션 의 승패가 이미 정해져 있는지 알아내는 것입니다. 만약 이게 가능하다면, 우리는 끝말잇기 게임을 완전히 정복하는 셈입니다.
하지만 아쉽게도, 임의의 상황에서 승패를 100% 예측하는 것은 현대 컴퓨터로도 매우 어려운 문제로 알려져 있습니다.
그렇다고 실망할 필요는 없습니다. 모든 상황은 아니더라도, 승패가 명확하게 결정되는 '특수한 상황'들이 존재하기 때문이죠. 저희 끝말잇기 엔진이 '승리', '패배', '순환'으로 분류하는 음절들이 바로 그런 경우입니다.
이제부터 우리는 전체 단어의 그래프()는 고정해두고, 그 안의 각 음절()들이 이런 '특수한 상황'에 해당하는지, 즉 승패를 빠르게 알아낼 수 있는지 판별하는 방법을 알아볼 것입니다. 앞으로는 편의상 "포지션 가 필승이다"라는 말 대신, 간단히 "는 필승 음절이다"라고 부르겠습니다.
가장 먼저, 필승 전략에 복잡한 '사이클'이 포함되지 않는 간단한 경우부터 살펴보겠습니다. 이 알고리즘은 마치 도미노처럼 한 음절의 승패가 다른 음절의 승패를 연쇄적으로 결정짓는 원리를 이용합니다.
가장 확실한 패배부터 찾아봅시다. 바로 더 이상 말을 이을 단어가 없는 '막다른 길' 음절입니다. '나트륨'의 '륨', '기쁨'의 '쁨'처럼, 이 글자로 단어를 받아버리면 다음 말을 할 수 없어 무조건 지게 되죠.
이런 '막다른 길' 음절들은 고민할 필요도 없이 필패(Losing) 음절입니다.
'륨'이 필패라는 사실을 알게 되면, '나트륨'이나 '베릴륨'처럼 상대에게 '륨'을 넘겨줄 수 있는 단어는 아주 좋은 '이기는 수'가 됩니다. 즉, 이런 수를 둘 수 있는 '나'나 '베' 같은 음절은 필승(Winning) 음절이 되는 것이죠.
규칙 1: 필패 음절로 이어지는 단어를 낼 수 있는 음절은 필승 음절이다.
반대의 경우도 있습니다. 예를 들어 '늣'으로 시작하는 단어가 사전에 '늣치' 하나뿐이라고 가정해봅시다. '늣'을 받은 플레이어는 어쩔 수 없이 '늣치'를 말해야 하고, 상대방에게 필승 음절인 '치'를 넘겨주게 됩니다. 결국 '늣'을 받은 플레이어는 지게 되므로, '늣'은 필패 음절입니다.
규칙 2: 내가 가진 모든 선택지(단어)가 상대방의 필승으로 이어진다면, 현재 내 음절은 필패 음절이다.
'사이클 없는 승패 전파'는 이 과정의 반복입니다.
이 알고리즘은 승패가 결정된 음절을 그래프에서 제거하는 '가지치기(Pruning)'를 통해 더욱 강력하고 단순해집니다.
'가지치기'는 알고리즘 자체를 매우 효과적으로 단순화합니다. 예를 들어, 필승 음절인 '치'가 그래프에서 제거되면, '치'로 향하던 '늣치'라는 단어(엣지)도 함께 사라집니다. 그 결과, '늣'은 더 이상 갈 곳이 없는 새로운 '막다른 길' 정점이 되어 필패로 판정됩니다.
따라서 '어떤 정점에서 시작하는 모든 단어가 필승 음절로 이어지는가?' 와 같은 복잡한 조건을 확인할 필요 없이, 그저 '새롭게 막다른 길이 된 정점이 있는가?'만 계속 확인하면 되는 것입니다.
결과적으로, 전체 알고리즘은 아래 두 과정의 반복으로 매우 단순화됩니다.
이 과정을 더 이상 그래프에 변화가 없을 때까지 계속 반복합니다.
가지치기는 단순히 이미 분석이 끝난 음절을 정리하는 것 이상의 중요한 이점을 가집니다. 이렇게 불필요한 가지들을 미리 잘라내면, 전체 그래프의 크기가 줄어들어 이후에 있을 더 복잡한 분석(예: 돌림 단어 검출)의 속도를 크게 향상시킬 수 있습니다.